package 极客算法训练营.chapter11;

/**
 * 输入：nums = [4,5,6,7,0,1,2], target = 3
 * 输出：-1
 */
public class 搜索旋转排序数组 {

    //有10多个用例过不了
    class Solution0 {
        public int search(int[] nums, int target) {
            int left = 0, right = nums.length - 1, mid = 0;
            while (left <= right) {
                mid = (left + right) / 2;
                if (nums[left] >= nums[right]) {
                    if (target <= nums[right]) {
                        left = mid + 1;
                    } else {
                        right = mid - 1;
                    }
                } else if (nums[left] <= nums[right]) {
                    if (nums[mid] == target) {
                        return mid;
                    } else if (nums[mid] > target) {
                        right = mid - 1;
                    } else {
                        left = mid + 1;
                    }
                }
            }
            return mid;
        }
    }

    class Solution {
        public int search(int[] nums, int target) {
            int length = nums.length;
            if (length == 0) return -1;
            if (length == 1) {
                return target == nums[0] ? 0 : -1;
            }
            int left = 0, right = length - 1, mid = 0;
            //总体原则，在无序中找有序
            while (left <= right) {
                mid = (left + right) / 2;
                if (nums[mid] == target) return mid;
                //mid在左半部分
                if (nums[mid] >= nums[0]) {
                    //target在有序部分
                    if (nums[0] <= target && target <= nums[mid]) {
                        right = mid - 1;
                    } else {
                        left = mid + 1;
                    }
                } else {
                    //mid在右半部分
                    if (nums[mid] <= target && target <= nums[length - 1]) {
                        left = mid + 1;
                    } else {
                        right = mid - 1;
                    }
                }
            }
            return -1;
        }
    }
}
